#
# @lc app=leetcode.cn id=76 lang=python3
#
# [76] 最小覆盖子串
#

# @lc code=start
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 处理特殊情况
        if not s or not t or len(s)<len(t):
            return ""
        # 字典统计储存字符个数
        need, have = {}, {}
        for chr in s:
            have[chr] = 0 # 初始化为0
            need[chr] = 0
        for chr in t:
            need[chr] = need.get(chr, 0) + 1
        # 左,右指针初始化
        left, right = 0, 0
        min_len = len(s) + 1 # ?细节
        cnt=0 # 当前取得的子串中,用于覆盖t的字符个数
        start = 0 # 最小覆盖子串在原字符串中的起始位置
        while right < len(s):
            # 右移直到覆盖字串
            r_chr = s[right]
            if need[r_chr] == 0:
                right+=1
                continue
            # 新添加的字符是字串需要的,计数cnt+=1
            if have[r_chr] < need[r_chr]:
                cnt += 1
            have[r_chr] += 1
            right += 1 # 右移直到覆盖子串
            while cnt == len(t): # 满足覆盖字串
                if right-left < min_len:
                    min_len = right-left
                    start = left
                # 缩短覆盖子串到最小覆盖子串
                l_chr= s[left]
                if need[l_chr] == 0: # 左边界字符不需要
                    left += 1
                    continue
                # 缩短到刚刚满足覆盖子串
                if have[l_chr] == need[l_chr]:
                    cnt -= 1
                have[l_chr] -= 1
                left += 1
        # 如果最小长度还为初始值，说明没有符合条件的子串
        if min_len == len(s)+1:
            return ""
        
        return s[start: start+min_len]


             
            


# @lc code=end

